emscripten
Downloading...

Resize canvas Lock/hide mouse pointer    


/ >> augmented_containers >> augmented_sequence_t
jhcarl0814.github.io
	Augmented Containers
		Sequence
			augmented_*****_t
			augmented_deque_t
		Associative
			augmented_***​/​***​/​********​/​********_t (has-a augmented_sequence_t)
		*****
			augmented_*****_t

augmented_containers::augmented_sequence_t

enum class augmented_sequence_physical_representation_e {
	rb3p,
	rb2p,
	finger_tree, };
enum class augmented_sequence_size_management_e {
	no_size,
	at_node_end,
	at_each_node_except_node_end,
};
template<
	typename element_t,
	typename allocator_t = std::allocator<element_t>,
	typename accumulator_t_ = augmented_sequence_helpers::empty_accumulator_t,
	typename augmented_sequence_physical_representation_t = std::integral_constant<augmented_sequence_physical_representation_e, augmented_sequence_physical_representation_e::rb3p>,
	typename augmented_sequence_size_management_t = std::integral_constant<augmented_sequence_size_management_e, augmented_sequence_size_management_e::at_each_node_except_node_end>
> struct augmented_sequence_t;
#include<augmented_containers/augmented_rb2p.hpp> (one single header file library)
template<
	typename element_t,
	typename allocator_t,
	typename accumulator_t,
	typename augmented_sequence_physical_representation_t,
	typename augmented_sequence_size_management_t
> requires(static_cast<augmented_sequence_physical_representation_e>(augmented_sequence_physical_representation_t{}) == augmented_sequence_physical_representation_e::rb2p)
struct augmented_sequence_t;
#include<augmented_containers/augmented_rb3p.hpp> (one single header file library)
template<
	typename element_t,
	typename allocator_t,
	typename accumulator_t,
	typename augmented_sequence_physical_representation_t,
	typename augmented_sequence_size_management_t
> requires(static_cast<augmented_sequence_physical_representation_e>(augmented_sequence_physical_representation_t{}) == augmented_sequence_physical_representation_e::rb3p)
struct augmented_sequence_t;

augmented_sequence_t is an augmented, general-purpose sequence. It's part of the augmented containers library, providing a more powerful version of sequence containers (let containers (and possibly its subranges) always have several accompanying results of algorithms/views), as well as <algorithm> and <ranges> (when the input sequence changes, refresh output values/ranges in logarithmic time complexity). To help understand what kind of problems the library solves: Dynamic problem (algorithms) - Wikipedia, Augmented map - Wikipedia.

Physical representations and Size management

members
iterator::operator++
iterator::operator--
split_emit_left
split_emit_right
physical
representation
red-black tree
two pointers per node
O(1) In the first round of split operation, spends O(1) time to get insert position in the subtree.
red-black tree
three pointers per node
O(lg(N)) (amortized O(1)) At the beginning of split operation, spends O(lg(N)) time to get predecessor of the element at the split position.
In the first round of split operation, spends O(lg(N)) time to get insert position in the subtree.
members
size iterator split_emit_left
split_emit_right
size
management
does not store size not supported
stores size at end node At the end of split operation, spends O(distance(rangeemitted)) time to restore the sizes.
stores subtree sizes at each node except node end Can calculate its index and provides all operations syntactically required by std::random_access_iterator, all take O(lg(N)) time.
iterator::iterator_concept is still std::bidirectional_iterator_tag because of time complexity requirements.

Examples

The untagged pointers are drawn as solid lines. The 0b1-tagged pointers are drawn as dashed lines.

In rb3p's examples, end node's child_right, parent and child_left are drawn separately to not break graphviz's layout.

In rb2p's examples, non-end node's loop (node's my_list_beign() → node's child_right, node's child_right's next() → node's leftmost_descendent_of_child_right, node's leftmost_descendent_of_child_right's my_list_begin() → node's rightmost_descendent_of_child_left, node's rightmost_descendent_of_child_left's my_list_beign() → node's child_left, node's child_left's next() → node, the last edge of the loop is 0b1-tagged) has it's edges drawn end-to-end to make it clearer (the pointers are still pointing to whole nodes, not members of nodes).

In rb2p's examples, end node's loop (end node's my_list_beign() → leftmost_descendent_of_root, leftmost_descendent_of_root's my_list_beign() → root, root's next() → rightmost_descendent_of_root, rightmost_descendent_of_root's my_list_beign() → end_node, the last edge of the loop is 0b1-tagged) is not drawn to not break graphviz's layout.

In rb2p's examples, end node has my_list_beign_, non-end node has my_list_beign_ and next_. The bit210 of my_list_beign_ stores the role of the node (there are 8 roles: end, root, child_left_not_a_leftmost_descendent, child_left_leftmost_descendent_of_non_root, child_left_leftmost_descendent_of_root, child_right_not_a_rightmost_descendent, child_right_rightmost_descendent_of_non_root, child_right_rightmost_descendent_of_root), the other bits are used to store my_list_beign(). The bit2 of next_ stores the color of the node (reflected on the color of table cells' borders), the bit1 of next_ stores whether my_list_beign() is 0b1-tagged, the bit0 of next_ stores whether next() is 0b1-tagged, the other bits are used to store next().

empty

The accumulation step is skipped. What's left (when augmented_sequence_size_management_t is augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end) can be seen as a std::vector/std::deque that supports fast split/concatenate and never invalidates iterators/references/pointers, or a std::list with random access ability.

augmented_containers::augmented_sequence_t<
	char,
	std::allocator<char>,
	augmented_containers::augmented_sequence_helpers::empty_accumulator_t,
	...
> augmented_sequence;
static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​)
augmented_containers​::​augmented_sequence_size_management_e​::​no_size augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end
static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p
augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p

accumulator_yield_one_value

element_t(char)s are accumulated into accumulated_storage_t(std::string)s.

augmented_containers::augmented_sequence_t<
	char,
	std::allocator<char>,
	augmented_containers::augmented_sequence_helpers::accumulator_sequence_t<char, std::string>,
	...
> augmented_sequence;
static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​)
augmented_containers​::​augmented_sequence_size_management_e​::​no_size augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end
static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p
augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p

accumulator_yield_multiple_values

element_t(int)s' addresses and arrays thereof are accumulated into their std::ranges::merge | std::views::take(3) (stores addresses so you can modify the original elements).

augmented_containers::augmented_sequence_t<
	int,
	std::allocator<int>,
	augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<accumulating_min_n_element_binary_functor_t<int, 3, true>>,
	...
> augmented_sequence;
static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​)
augmented_containers​::​augmented_sequence_size_management_e​::​no_size augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end
static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p
augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p

accumulator_yield_one_view

Each element_t(int)'s corresponding accumulated_storage_t comes with the navigator portion (prev and next pointers) to be ready to form a circular doubly linked list. The accumulator takes chunk-begins (std::ranges::prev(it).is_end() || (*std::ranges::prev(it) < 50) != (*it < 50)), discards non-chunk-begins (and takes other accumulated circular doubly linked lists), accumulates them into a circular doubly linked lists representing std::ranges::chunk_by_view of the original sequence.

augmented_containers::augmented_sequence_t<
	int,
	std::allocator<int>,
	diffing_adjacent_element_accumulator_t,
	...
> augmented_sequence;
static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​)
augmented_containers​::​augmented_sequence_size_management_e​::​no_size augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end
static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p
augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p

accumulator_yield_multiple_views

Similar to the accumulator_yield_one_view example, except that each accumulated_storage_t has "a map from element % 3 to circular doubly linked list's end node" (instead of just "one end node"). The result represents C++32's std::ranges::group_by_view of the original sequence (navigator_style = std::ranges::group_by_view::navigator_style_t::circular_doubly_linked_list, map_container_tt = std::map).

augmented_containers::augmented_sequence_t<
	int,
	std::allocator<int>,
	group_by_element_accumulator_t,
	...
> augmented_sequence;
static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​)
augmented_containers​::​augmented_sequence_size_management_e​::​no_size augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end
static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p
augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p

find_by_monotonic_predicate

element_t(std::string)s' .size()s are accumulated by std::size_t operator+(std::size_t, std::size_t). Use .find_by_monotonic_predicate([&](){ ... }) to find the first element where the accumulated_storage_t(std::size_t) (accumulated string size so far) starts to be greater than the given character index, i.e., the element that contains the the given character indexth character. Note that the hierarchical structure saves time by skiping substructures that don't contain the results.

augmented_containers::augmented_sequence_t<
    std::string,
    std::allocator<std::string>,
    augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<accumulating_binary_functor_string_length>,
	...
> augmented_sequence;
static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​)
augmented_containers​::​augmented_sequence_size_management_e​::​no_size augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end
static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p
augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p

find_by_heap_predicate

element_t(int)s are accumulated into their std::ranges::max. Use .find_by_heap_predicate(jts_output, [&](){ ... }) to eagerly find all elements greater than or equal to the given threshold. Note that the hierarchical structure saves time by skiping substructures that don't contain the results. It's possible to parallelize the search, depending on the availability of std::execution.

augmented_containers::augmented_sequence_t<
    int,
    std::allocator<int>,
    augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<augmented_containers::augmented_sequence_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<int, augmented_containers::augmented_sequence_helpers::max_t<int>>>,
	...
> augmented_sequence;
static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​)
augmented_containers​::​augmented_sequence_size_management_e​::​no_size augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end
static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p
augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p

find_by_heap_predicate_generator

element_t(int)s are accumulated into their std::ranges::max. Use .find_by_heap_predicate_generator([&](){ ... }) to lazily iterate through elements greater than or equal to the given threshold, until an element divisible by the given denominator is encountered. Note that the hierarchical structure saves time by skiping substructures that don't contain the results. It's possible to parallelize the search, depending on the availability of std::execution.

augmented_containers::augmented_sequence_t<
    int,
    std::allocator<int>,
    augmented_containers::augmented_sequence_helpers::accumulator_wrapping_accumulating_binary_functor_t<augmented_containers::augmented_sequence_helpers::accumulating_binary_functor_wrapping_homogeneous_binary_functor_t<int, augmented_containers::augmented_sequence_helpers::max_t<int>>>,
	...
> augmented_sequence;
static_cast​<​augmented_containers​::​augmented_sequence_size_management_e​>​(​augmented_sequence_size_management_t​{​}​)
augmented_containers​::​augmented_sequence_size_management_e​::​no_size augmented_containers​::​augmented_sequence_size_management_e​::​at_node_end augmented_containers​::​augmented_sequence_size_management_e​::​at_each_node_except_node_end
static_cast​<​augmented_containers​::​augmented_sequence_physical_representation_e​>​(​augmented_sequence_physical_representation_t​{​}​) augmented_containers​::​augmented_sequence_physical_representation_e​::​rb2p
augmented_containers​::​augmented_sequence_physical_representation_e​::​rb3p